package _07_priority_queue.my_implements;

import _00_my.exception.TechnicalLimitationException;
import _04_queue.AbstractQueue;
import _07_priority_queue.Priority;

import java.util.Iterator;

/**
 * @author: mornd
 * @dateTime: 2023/6/8 - 15:59
 * 基于大顶堆(完全二叉树)实现，大的在顶部
 * O(log n)
 */
public class MaxHeap<E extends Priority> extends AbstractQueue<E> {
    Priority[] data;
    int size;

    public MaxHeap(int capacity) {
        data = new Priority[capacity];
    }

    /**
     * 1、入队新元素时，加入到数组的末尾（c）
     * 2、（上浮）不断比较c与它父节点（p）的优先级
     * - 如果p优先级低，则p向下移动，将p值赋给c，并找到下一个 p
     * - 直至p优先级更高 或者c的下标=0 为止
     *
     * @param e
     * @return
     */
    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }

        // 最后新元素插入的下标
        int c = size;
        // 父节点的下标
        int p;

        while (c > 0 &&
                data[p = getParent(c)].priority() < e.priority()) {
            // 父节点向下移动
            data[c] = data[p];
            c = p;
        }

        data[c] = e;
        size++;
        return true;
    }

    /**
     * 求出下标 i 的父节点下标
     *
     * @param i -1 表示该节点没有分节点了
     * @return
     */
    private int getParent(int i) {
        if (i > 0) {
            // 此公式只有i大于0才生效
//            return  (int) Math.floor((i - 1) >>> 1);
            return (i - 1 >>> 1);
        }
        return -1;
    }

    /**
     * 出列步骤：
     * 1、下标0的元素出队，尾部元素替换下标0元素，尾下标制空
     * 2、（下潜）从顶部p开始，找到其左孩子和右孩子中较大的孩子(c)，依次将c元素替换掉p, c=p
     * 直至p没有孩子或者两个孩子的值都比它小为止
     *
     * @return
     */
    @Override
    public E poll() {
        if (super.isEmpty()) {
            return null;
        }
        Priority e = data[0];
        size--;
        // 将尾部替换掉头部
        data[0] = data[size];

        // 下潜
        diving2(0);

        data[size] = null;
        return (E) e;
    }

    /**
     * 下潜节点
     *
     * @param p 需要下潜节点的下标
     */
    @Deprecated
    private void diving(int p) {
        Priority top = data[p];
        // 左右子节点下标
        int l, r;
        // 屎山代码
        while ((l = (2 * p + 1)) < size | (r = (l + 1)) < size) {
            if (l >= size) {
                // 左空，右非空
                if (data[p].priority() < data[r].priority()) {
                    data[p] = data[r];
                    // 父节点小于右子节点
                    p = r;
                } else {
                    break;
                }
            } else if (r >= size) {
                // 左非空，右空
                if (data[p].priority() < data[l].priority()) {
                    data[p] = data[l];
                    p = l;
                } else {
                    break;
                }
            } else {
                // 左右都非空
                if (data[r].priority() < data[l].priority()) {
                    if (data[p].priority() < data[l].priority()) {
                        data[p] = data[l];
                        p = l;
                    } else {
                        break;
                    }
                } else if (data[p].priority() < data[r].priority()) {
                    data[p] = data[r];
                    p = r;
                } else {
                    break;
                }
            }
        }
        if (p != 0) {
            data[p] = top;
        }
    }


    /**
     * 优化后的下潜
     *
     * @param p
     */
    private void diving2(int p) {
        int top = p;
        int max = top;

        do {
            /*
                根据父节点下标top，求出左右子节点下标？
                left：   2 * top + 1
                right：  2 * top + 2
             */
            int l = 2 * top + 1;
            int r = l + 1;

            if (l < size && data[l].priority() > data[max].priority()) {
                max = l;
            }
            if (r < size && data[r].priority() > data[max].priority()) {
                max = r;
            }

            if (max != top) {
                swap(top, max);
                top = max;
            }
        } while (max != top);
    }

    /**
     * 递归实现下潜
     *
     * @param p
     */
    private void diving3(int p) {
        int max = p;
        int l = 2 * p + 1;
        int r = l + 1;

        if (l < size && data[l].priority() > data[max].priority()) {
            max = l;
        }
        if (r < size && data[r].priority() > data[max].priority()) {
            max = r;
        }
        if (p != max) {
            swap(p, max);
            diving3(max);
        }
    }

    private void swap(int i, int j) {
        Priority t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    @Override
    public E peek() {
        if (super.isEmpty()) {
            return null;
        }
        return (E) data[0];
    }

    @Override
    public boolean isFull() {
        return size == data.length;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        throw new TechnicalLimitationException();
    }
}
